1. Field of the Invention
The present invention relates generally to a mobile communication system, and in particular, to a resource allocation method in a multicarrier communication system.
2. Description of the Related Art
Along with the development of mobile communication technology, diverse and complex resource allocation techniques have been proposed to optimize system performance. Before packet-based architecture, a voice cellular network allocated one dedicated channel per user when requesting resources. With packet-based architecture, however, a plurality of users shares a single channel for communications.
FIG. 1 illustrates resource allocation in a conventional single-channel sharing scheme. Referring to FIG. 1, a scheduler 103 in a base station (BS) prioritizes mobile stations 105a to 105d based on their feedback channel status information. The scheduler 103 multiplexes data temporarily stored in transmission buffers 102a to 102d for the respective mobile stations 105a to 105d according to their priority levels using a channel allocator 104 and transmits the multiplexed data through a transmit antenna 106.
In the above single-channel sharing communication system, system performance depends on scheduling. Despite good-performance scheduling, there are limits on high-speed data transmission since there is only a single channel shared among a plurality of users.
A system based on the next-generation communication technology, OFDM (Orthogonal Frequency Division Multiplexing) can configure multiple channels by means of a plurality of orthogonal subcarriers, which renders resource allocation more flexible. Also, when a MIMO (Multiple Input Multiple Output) scheme or an array antenna is used, resources can be allocated to a plurality of users simultaneously.
One new trend in the mobile communication technology is direct feedback of the channel status information of each channel from a mobile station.
In a high-speed wireless communication system like CDMA HDR (Code Division Multiple Access High Data Rate), a mobile station feeds channel status measurement back to the base station. Based on the channel status information, a base station schedules data for transmission and applies an appropriate modulation and coding to each channel. Along with the increasing number of channels, the volume of information directed from the mobile station to the base station increases, and each base station needs to allocate two or more channels to achieve diversity, in the next-generation wireless communication system. Hence, there is a need for effectively allocating resources when each user requests two or more channels.
For the OFDM system, an optimal resource allocation that maximizes the system throughput can be found by trying all possible combinations. Yet, the computational complexity of finding the optimal resource allocation is NP-hard (Non-deterministic Polynomial-time hard). “NP-hard” is a well known term in computational complexity theory, NP-hard refers to the class of decision problems that contains all problems H such that for every decision problem L in NP there exists a polynomial-time many-one reduction to H, written L=<H. Thus, its practical implementation is impossible.